a11y: Consolidate the attributes container

While we have split the various attributes for convenience, there's no
reason why we should have specialised data types for the attributes
container object.

a11y: Add relations API

Since we split relation attributes from the generic properties, we need
to add API for setting and retrieving their values.

a11y: Simplify GtkAccessibleValue

Reduce the amount of subclassing, by handling collection of fundamental
types directly from the generic code paths. We now handle boolean,
tristate, integer, number, string, and relation values in the generic
code path; if an attribute supports the "undefined" value, we return the
undefined value singleton.

a11y: Resync with the ARIA spec

Drop roles and properties that were deprecated in WAI-ARIA 1.1, and add
new roles and properties defined in WAI-ARIA 1.2 and later.

We also split the relationship properties into their own enumeration, so
we can keep the GtkAccessibleProperty type more compact.

Remove GTK_ACCESSIBLE_STATE_NONE

It's pointless, we can use an explicit value of `-1` everywhere.
Additionally, it complicates all code that uses the state enumeration as
an array index, since now we need to guard against a negative offset.

a11y: Add binding-friendly accessible property setter

Matching the one for the accessible state.

a11y: Collect reference value

Some properties that take a reference to an accessible haven't been
updated to collect the correct type.

a11y: Update the accessible label for GtkButton

a11y: Update GtkSeparator

Add an accessible role, and update the orientation state.

a11y: Set the role for GtkScale

a11y: Update the accessible state for GtkRange

a11y: Update the "pressed" state on toggle buttons

a11y: Add roles to various widgets

Add accessible properties to GtkAccessible

We propagate the accessible state and properties to each ATContext in
the same virtual function, since they are functionally similar.

Add GtkAccessiblePropertySet

Like GtkAccessibleStateSet, the PropertySet is a set for accessible
properties.

Plumb all the GtkAccessibleProperty values into GtkAccessibleValue

Similarly to how we deal with GtkAccessibleState.

Allow setting the accessible role at construction

Some widgets have different accessible roles depending on some
parameter, so we cannot set the role at class init time. For those
widgets, we add an "accessible-role" property to GtkAccessible, and we
allow setting it (only) at construction time.

Start documenting the Accessibility API

Add the introductory text from #2833, and the various types to the API
reference.

Update the accessible state on widget visibility changes

The GTK_ACCESSIBLE_STATE_HIDDEN has the opposite meaning of the
GtkWidget:visible property.

Have GtkWidget implement GtkAccessible

Each widget type has an accessible role associated to its class, as
roles cannot change during the life time of a widget instance.

Each widget is also responsible for creating an ATContext, to proxy
state changes to the underlying accessibility infrastructure.

Plug GtkATContext into GtkAccessible

An Accessible implementation must create an ATContext object. UI
elements are supposed to interact with the GtkAccessible API, but we
expose GtkATContext to allow patterns like delegation.

Add GtkATContext

The ATContext type is meant to be used as the base class for
implementations of the assistive technology API—the actual mechanism
needed to communicate to components like the screen reader, or any other
AT.

Every time the widget state changes, the ATContext is meant to broadcast
the state change; and every time the AT queries the state of a UI
element, the ATContext is meant to provide that information.

We also have a "test" ATContext implementation, which is meant to be
used to write tests to verify that changes are propagated without
requiring a whole desktop session.

Add GtkAccessibleStateSet

Since states can be set or unset, we need a container type that has all
the possible states, and a bitmask that tells us which ones are set.

Add GtkAccessibleValue

All accessible properties and states may have one of the following
types:

 - true/false
 - true/false/undefined
 - true/false/mixed/undefined
 - reference (to another UI element)
 - reference list
 - integer
 - number (real numerical value)
 - string
 - token (one of a limited set of allowed values)
 - token list

See: https://www.w3.org/WAI/PF/aria/states_and_properties#propcharacteristic_value

The GtkAccessibleValue is a simple reference counted type that can be
"subclassed" to implement each value type.

This initial commit adds GtkAccessibleValue and the basic subclasses for
plain boolean, tristate (true/false/undefined), and token types,
including statically allocated values that can be shared instead of
allocated.

Introduce GtkAccessible

GtkAccessible is an interface for accessible UI elements.

Currently, it doesn't do much except exist as a type; in the future, it
will be the entry point for all accessible state in GTK.

a11y: Add the supported accessibility roles

The list of roles is taken from the WAI-ARIA 1.2 specification:

  https://w3c.github.io/aria/

Some of these roles do not make entirely sense from a GTK application
perspective, but we can remove them before finalizing the API.

Remove ATK

To build a better world sometimes means having to tear the old one down.
        -- Alexander Pierce, "Captain America: The Winter Soldier"

ATK served us well for nearly 20 years, but the world has changed, and
GTK has changed with it. Now ATK is mostly a hindrance towards improving
the accessibility stack:

 - it maps to a very specific implementation, AT-SPI, which is Linux and
   Unix specific
 - it requires implementing the same functionality in three different
   layers of the stack: AT-SPI, ATK, and GTK
 - only GTK uses it; every other Linux and Unix toolkit and application
   talks to AT-SPI directly, including assistive technologies

Sadly, we cannot incrementally port GTK to a new accessibility stack;
since ATK insulates us entirely from the underlying implementation, we
cannot replace it piecemeal. Instead, we're going to remove everything
and then incrementally build on a clean slate:

 - add an "accessible" interface, implemented by GTK objects directly,
   which describe the accessible role and state changes for every UI
   element
 - add an "assistive technology context" to proxy a native accessibility
   API, and assign it to every widget
 - implement the AT context depending on the platform

For more information, see: https://gitlab.gnome.org/GNOME/gtk/-/issues/2833

Merge branch 'wip/otte/boolfilter' into 'master'

Add GtkBoolFilter

See merge request GNOME/gtk!2288

Update Catalan translation

Add GtkBoolFilter

Takes a boolean GtkExpression (like a boolean object property) to run a
filter with.

Merge branch 'matthiasc/for-master' into 'master'

overlaylayout: Document minimally

See merge request GNOME/gtk!2285

overlaylayout: Document minimally

This layout manager is not reusable, but we
still need to make its layout properties show
up in the docs.

Merge branch 'matthiasc/for-master' into 'master'

Matthiasc/for master

See merge request GNOME/gtk!2284

gtk: Improve struct packing in places

Plug some holes in our structs by rearranging
a few fields. This is was done looking at
pahole output.

gdk: Improve struct packing in places

Plug some holes in our structs by rearranging
a few fields. This is was done looking at
pahole output.

colorswatch: Remove unused radius fields

The radius fields are never used.

hsla: Just store floats

We are using floats for rgb, and we don't need more precision
for hsl colors either. We use hsl for computing color expressions
like shade(), lighter() and darker(), which are not precisely
specified anyway.

This commit updates the one test where the output changes a
tiny bit due to this.

headerbar: Drop the Private struct

colorplane: Drop the Private struct and padding

Merge branch 'matthiasc/for-master' into 'master'

Matthiasc/for master

See merge request GNOME/gtk!2283

Merge branch 'wip/otte/types' into 'master'

Get rid of unneeded glib types

See merge request GNOME/gtk!2282

Add another sortlistmodel test

This tests the crash fix in f7b73b2e010960975.

testsuite: Add an incremental sort test

Add a test that makes changes to a model while it
is incrementally sorted.

timsort: Avoid a crash

We need to clear the pointer after freeing the data,
since the sortlistmodel keeps its timsort structure
around and reuses it.

Replace "gdouble" with "double"

Replace "gfloat" with "float"

Replace "gchar" with "char"

Replace "gint" with "int"

testsuite: Use better names for sortlistmodel tests

Name the tests for what they do.

testsuite: Reenable tests for incremental sort

This was unintentionally disabled.

Merge branch 'remove-align-widget' into 'master'

menubutton: Remove align-widget property

See merge request GNOME/gtk!2280

sortlistmodel: Fix a crash

dropdown: Fix popup sizing

Setting a width request is not quite enough, since
gtk_widget_set_size_request() only queues a resize
when the widget is visible. Explicitly force one
here. Without this, the popup sometimes shows up
too small.

menubutton: Remove align-widget property

The property has been unused since commit 8701e34f749. That was four
years ago, so it's safe to say that nobody has been missing it terribly.

Merge branch 'fix-gdk-array-msvc' into 'master'

gdk/gdkarrayimpl.c: Fix build on Visual Studio

See merge request GNOME/gtk!2279

gdk/gdkarrayimpl.c: Fix build on Visual Studio

It seems like initializing something to an empty array using `{}` is a GCCism,
so just stuff a 0 within the braces to accomplish the same thing.

Merge branch 'matthiasc/for-master' into 'master'

filechooser: Remove a leftover signal emission

Closes #2942

See merge request GNOME/gtk!2276

docs: Work around escaping bugs

This is truly a russian doll of documentation formats:
a string containing <> inside an xml fragment in an |[ ]|
gtk-doc example in markdown in a doc comment.

Sadly, something gets escaping wrong, so the <> end up
literally in the docbook and mess up the last step of
our document formatting, even after turning them into
entities.

Work around this with an extra level of entities that
really shouldn't be necessary.

docs: Pass --standalone to pandoc

This flag causes pandoc to emit a proper doctype
declaration and, crucially, namespace declarations
for the xlink namespace that it insists on using
for href attributes. Without this, putting external
links in md documents doesn't survive the journey
through xml.

docs: Improve shortcut trigger docs

Point out the need to escape <> in xml.

docs: Explain the shortcutcontroller example a bit

Add a reference to the the syntax for shortcut actions
in builder files.

filechooser: Remove a leftover signal emission

Commit 0145809a94667c75ed4a4 replace the response-requested
signal with an action, but didn't actually remove the emission
of that no-longer-existing signal.

Fixes: #2942

Merge branch 'wip/otte/for-master' into 'master'

Wip/otte/for master

See merge request GNOME/gtk!2277

searchenginemodel: Remove unused code

searchengine: Remove unused set_recursive() call

Update Romanian translation

Update Romanian translation

Merge branch 'matthiasc/for-master' into 'master'

Matthiasc/for master

See merge request GNOME/gtk!2275

NEWS: Updates

migration guide: Add some tables

Add a table mapping event signals to their event controller
replacements, and a table mapping former GtkContainer
subclasses to their gtk_container_add replacement.

Merge branch 'wip/otte/for-master' into 'master'

timsort: Actually 0-terminate the array in get_runs()

See merge request GNOME/gtk!2274

timsort: Actually 0-terminate the array in get_runs()

This could cause SEGVs when changing the sort during an ongoing sort
operation.

Update Ukrainian translation

Update Ukrainian translation

Merge branch 'wip/otte/sortlistmodel2' into 'master'

Massively refactor and improve sortlistmodel

See merge request GNOME/gtk!2273

Update POTFILES.in

gtk-demo: Add a progress bar when the colors demo resorts

sortlistmodel: Add progress estimation

timsort: Add progress estimation

sortlistmodel: Make key generation part of the step function

SSave the missing keys as a bitset and iterate over that bitset in the
step function.

Solves the problem with a large UI block at the beginning of a sort
operation when all the keys were generated, in particular when key
generation was slow.

Benchmarks for maximum time taken by a single main loop callback:

     initial sort with complex GFileInfo keys
                       old      new
      32,000 items   137ms      3ms
     128,000 items   520ms     31ms

     initial sort with string keys
                       old      new
      32,000 items   187ms      1ms
     128,000 items   804ms      3ms

gtk-demo: Make colors demo do incremental sorting

sortlistmodel: Properly compute runs

When updating a (partially) sorted model, take the known runs for the
existing sort and apply them to the new sort. That way, we don't have to
check the whole model again.

Benchmarks:

      appending half the items to a model of strings
                        old      new
      512,000 items   437ms    389ms
    1,024,000 items  1006ms    914ms

      appending 10% of the items to a model of strings
                        old      new
      512,000 items   206ms    132ms
    1,024,000 items   438ms    301ms

      appending 1 item to a model of strings
                        old      new
       64,000 items   1.8ms   0.00ms
      512,000 items     ---   0.01ms

sortlistmodel: Make sort stable again

Previously, the sort was not stable when items were added/removed while
sorting or the sort algorithm was changed.

Now the sort looks at the item position (via the key's location in the
keys array) to make sure each comparison stays stable with respect to
this position.

multisorter: Implement GtkSortKeys

treelistrowsorter: Implement GtkSortKeys

numericsorter: Implement GtkSortKeys

stringsorter: Implement GtkSortKeys

sortkeys: Add an equal sort keys

Compares every element as equal.
This is useful when sorters are in an invalid configuration.

sortlistmodel: Use GtkSortKeys

This massively speeds up sorting with expensive sort functions that it's
the most worthwhile optimization of this whole branch.
It's slower for simple sort functions though.

It's also quite a lot slower when the model doesn't support sort keys
(like GtkCustomSorter), but all the other sorters do support keys.

Of course, this depends on the number of items in the model - the number
of comparisons scales O(N * log N) while the overhead for key handling
scales O(N).
So as the log N part grows, generating keys gets more and more
beneficial.

Benchmarks:

       initial sort of a GFileInfo model with display-name keys
                       items     keys
         8,000 items   715ms     50ms
        64,000 items     ---    554ms

       initial sort of a GFileInfo model with complex keys
                       items     keys
        64,000 items   340ms    295ms
       128,000 items   641ms    605ms

       removing half a GFileInfo model with display-name keys
       (no comparisons, just key freeing overhead of a complex sorter)
                       items     keys
       512,000 items    14ms     21ms
     2,048,000 items    40ms     62ms

       removing half a GFileInfo model with complex keys
       (no comparisons, just key freeing overhead of a complex sorter)
                       items     keys
       512,000 items    90ms    237ms
     2,048,000 items   247ms    601ms

sorter: Introduce GtkSortKeys

GtkSortKeys is an immutable struct that can be used to manage "sort
keys" for items.

Sort keys are memory that is created specifically for sorting. Because
sorting involves lots of comparisons, it's a good idea to prepare the
data relevant for sorting in advance and sort on that data.

In measurements with a PropertyExpression on a string sorter, it's about
??? faster

sortlistmodel: Split the SortItem into 2 arrays

Instead of one item keeping the item + its position and sorting that
list, keep the items in 1 array and put the positions into a 2nd array.

This is generally slower while sorting, but allows multiple improvements:

1. We can replace items with keys
   This allows avoiding multiple slow lookups when using complex
   comparisons

2. We can keep multiple position arrays
   This allows doing a sorting in the background without actually
   emitting items-changed() until the array is completely sorted.

3. The main list tracks the items in the original model
   So only a single memmove() is necessary there, while the old version
   had to upgrade the position in every item.
Benchmarks:

        sorting a model of simple strings
                          old      new
        256,000 items   256ms    268ms
        512,000 items   569ms    638ms

        sorting a model of file trees, directories first, by size
                          old      new
         64,000 items   350ms    364ms
        128,000 items   667ms    691ms

        removing half the model
                          old      new
        512,000 items    24ms     15ms
      1,024,000 items    49ms     25ms

sortlistmodel: Add an incremental property

Also refactor a large part of the sortmodel to make this convenient.

A large amount of time has been spent on getting items-changed regions
minimized.

testsuite: Add exhaustive sortlistmodel test

This is basically a copy/paste from the filterlistmodel test, but
adapted for sorting.

sortlistmodel: Make the sort callback useful

1. Run step() for a while to avoid very short steps
   This way, we batch items-changed() emissions.

2. Track the change region accurately
   This way, we can avoid invalidating the whole list if our step just
   touched a small part of a huge list.
   As this is a merge sort, this is a common occurence when we're buys
   merging chunks: The rest of the model outside those chunks isn't
   changed.

Note that the tracking is accurate: It determines the minimum change
region in the model.

This will be important, because the testsuite is going to test this.

timsort: Add change tracking to gtk_tim_sort_step()

timsort: Add gtk_tim_sort_set_max_merge_size()

Makes the SOrtListModel responsive when incrementally sorting.

By making it configurable we can avoid losting performance in the
non-incremental case.

timsort: Make sure merges don't take too long

Limit the size of the merged areas and thereby chunk larger merges into
smaller ones.

sortlistmodel: Make sorting incremental

This is just an experiment so far to see how long it takes to sort.

timsort: Add gtk_tim_sort_set_runs()

... and use it in the SortListModel

Setting runs allows declaring already sorted regions so the sort does
not attempt to sort them again.

This massively speeds up partial inserts where we can reuse the sorted
model as a run and only resort the newly inserted parts.

Benchmarks:

    appending half the model
                    qsort  timsort
    128,000 items    94ms     69ms
    256,000 items   202ms    143ms
    512,000 items   488ms    328ms

    appending 1 item
                    qsort  timsort
      8,000 items   1.5ms    0.0ms
     16,000 items   3.1ms    0.0ms
              ...
    512,000 items     ---    1.8ms

sortlistmodel: Use timsort

Simply replace the old qsort() call with a timsort() call.

This is ultimately relevant because timsort is a LOT faster in merging
to already sorted lists (think items-chaged adding some items) or
reversing an existing list (think columnview sort order changes).

Benchmarks:

    initially sorting the model
                    qsort  timsort
    128,000 items   124ms    111ms
    256,000 items   264ms    250ms